Компьютерная сеть состоит из связанных между собой двусторонними кана­лами связи N компьютеров, номера которых от 1 до N. Эта сеть предна­значена для распространения сообщения от центрального компьютера всем остальным. Компью­тер, получивший сообщение, владеет им и может распро­странять его дальше по сети. Запрещается передавать сообщение на один и тот же компьютер дважды. Время пе­редачи сообщения по каналу связи зани­мает одну секунду, при этом передающий и принимающий компьютеры заня­ты на все время передачи данного сообщения. На рис. приведен возможный вариант такой сети.

Рис.

В начальный момент времени центральный компьютер может передавать со­общение одному из непосредственно связанных с ним компьютеров, т.е. со­седу. После окончания передачи, этим сообщением будут владеть оба компь­ютера. Каж­дый из них может передать сообщение одному из своих соседей и так далее, пока все компьютеры не будут владеть сообщением.

Для сети, показанной на рис.1, возможный порядок распространения со­обще­ния от центрального компьютера с номером 6 приведен в примере.

ПРИМЕР.

Секунда 1:        6->4

Секунда 2:        4->3

                          6->7

Секунда 3:        3->1

                          4->5

Секунда 4:        3->2

Написать программу, которая:

а) вводит описание сети, проверяет корректность этого описания и, в случае его некорректности, печатает соответствующее сообщение, заканчивая работу;

б) определяет и печатает какой-либо порядок распространения сообще­ния;

в) определяет и печатает порядок передачи сообщения за минимальное время (порядок распространения сообщения для сети на рис., приведенный в примере 1, яв­ляется оптимальным).

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ

1) N не превосходит 50, а количество каналов связи не превосходит N+5.

2) Программа должна запрашивать имя входного файла; в крайнем случае до­пускается ввод данных с клавиатуры.

3) Сеть задается набором из N+2 строк в следующем формате:

строка 1:                       число компьютеров в сети (N);

строка 2:                       список всех соседей компьютера 1 (представляется                                           набором чисел, разделенных пробелами);

строка 3:                       список всех соседей компьютера 2;

...

строка N+1:      список всех соседей компьютера N;

строка N+2:      номер центрального компьютера.

Так, приведенная на рис.1 сеть может быть представлена следующим об­разом:

7

2 3

1 3

1 4 2

6 5 3

4

7 4

6

6

4) Вывод результатов на экран должен быть таким, как в примере 1.

РАЗБАЛЛОВКА

1. Организация диалога с пользователем:               - 5 баллов.

2. Пункт А:                                                                                         - 25 баллов.

3. Пункт Б:                                                                                          - 25 баллов.

4. Пункт В:                                                                                          - 30 баллов.

5. Выполнение технических требований:                           - 15 баллов.